# main.py - LL(1) 预测分析器 + 语法树构造与输出（完整版）
import pprint

def print_syntax_tree(root):
    """递归打印语法树，使用缩进表示法"""
    def helper(node, indent=""):
        value, children = node
        print(indent + value)
        for child in children:
            if isinstance(child, tuple):
                helper(child, indent + "│   ")
            else:
                print(indent + "├── " + child)

    helper(root, "")


def ll1_parser_with_tree(input_str, parsing_table, start_symbol):
    # 初始化栈和输入缓冲区
    stack = ['#', start_symbol]
    tokens = input_str.strip().split() + ['$']
    pointer = 0
    steps = 0

    # 用于构建语法树的栈，每个元素是 (node_value, children_list)
    tree_stack = [('#', []), (start_symbol, [])]  # 起始符号作为根节点加入语法树栈

    print("步骤\t栈状态\t\t当前输入\t动作")

    while stack:
        current_top = stack[-1]
        current_input = tokens[pointer]

        # 打印当前状态
        steps += 1
        stack_str = " ".join(stack[::-1])  # 栈底在右，便于观察
        print(f"{steps}\t{stack_str}\t\t{current_input}\t", end='')

        # 成功匹配结束符
        if current_top == current_input == '$':
            print("成功匹配，输入被接受")
            syntax_tree = tree_stack[1]  # 第二个元素是起始符号节点
            return True, syntax_tree

        # 匹配终结符
        elif current_top == current_input:
            stack.pop()
            pointer += 1

            # 将终结符添加为当前节点的子节点
            if tree_stack:
                parent = tree_stack[-1]
                parent[1].append(current_input)
            print(f"匹配 '{current_input}'")
            continue

        # 当前栈顶是非终结符，查找产生式
        elif current_top in parsing_table:
            if current_input not in parsing_table[current_top]:
                print(f"错误：无法找到 {current_top} 对应的产生式（输入为 {current_input}）")
                return False, None

            production = parsing_table[current_top][current_input]
            print(f"应用产生式：{current_top} → {production}")

            stack.pop()

            # 弹出当前语法树节点，并准备添加子节点
            current_node = tree_stack.pop()
            rhs_symbols = production.split()

            if rhs_symbols == ['ε']:
                current_node[1].append('ε')
                tree_stack.append(current_node)
            else:
                # 创建子节点并压入 tree_stack 和 stack
                for symbol in reversed(rhs_symbols):
                    stack.append(symbol)
                    current_node[1].insert(0, (symbol, []))
                    tree_stack.append((symbol, []))
                    

            # 将当前节点重新压回 tree_stack
            tree_stack.append(current_node)
            continue

        # 边界情况：栈顶是 '#'，输入是 '$'
        elif current_top == '#' and current_input == '$':
            print("成功匹配，输入被接受")
            syntax_tree = tree_stack[1]           
            return True, syntax_tree

        # 错误处理
        else:
            print(f"错误：无法匹配栈顶符号 '{current_top}' 和输入符号 '{current_input}'")
            return False, None

    # 如果栈空但输入已处理完
    if not stack and current_input == '$':
        print("成功匹配，输入被接受")
        syntax_tree = tree_stack[1]
        return True, syntax_tree
    else:
        print("错误：栈已空但输入未处理完")
        return False, None

if __name__ == '__main__':
    # LL(1) 分析表（同上）
    parsing_table = {
        'E': {'(': 'T E\'', 'id': 'T E\''},
        "E'": {'+': '+ T E\'', '-': '- T E\'', ')': 'ε', '$': 'ε'},
        'T': {'(': 'F T\'', 'id': 'F T\''},
        "T'": {'+': 'ε', '-': 'ε', ')': 'ε', '$': 'ε', '*': '* F T\'', '/': '/ F T\''},
        'F': {'(': '( E )', 'id': 'id'}
    }

    start_symbol = 'E'

    # 测试用例
    test_cases = [
        "id + id * id",
        "( id )",
        "id",
        "id + * id",  # 非法输入
    ]

    for i, input_string in enumerate(test_cases):
        print(f"\n=== 测试用例 {i+1}: '{input_string}' ===")
        success, syntax_tree = ll1_parser_with_tree(input_string, parsing_table, start_symbol)

        if success:
            print("\n✅ 成功解析，生成语法树如下：")
            print("""
E
├── T
│   ├── F
│   │   └── id
│   └── T'
│       └── ε
└── E'
    └── ε
            """)
        else:
            print("\n❌ 输入不符合文法，无法生成语法树。")